lib/Mi manual de algoritmos/version_maraton_suramericana_2008/src/grafos/puntos_articulacion.cpp

   1 #include <vector>
   2 #include <set>
   3 #include <map>
   4 #include <algorithm>
   5 #include <iostream>
   6 #include <iterator>
   7
   8 using namespace std;
   9
  10 typedef string node;
  11 typedef map<node, vector<node> > graph;
  12 typedef char color;
  13
  14 const color WHITE = 0, GRAY = 1, BLACK = 2;
  15
  16 graph g;
  17 map<node, color> colors;
  18 map<node, int> d, low;
  19
  20 set<node> cameras;
  21
  22 int timeCount;
  23
  24 void dfs(node v, bool isRoot = true){
  25   colors[v] = GRAY;
  26   d[v] = low[v] = ++timeCount;
  27   vector<node> neighbors = g[v];
  28   int count = 0;
  29   for (int i=0; i<neighbors.size(); ++i){
  30     if (colors[neighbors[i]] == WHITE){ //  (v, neighbors[i]) is a tree edge
  31       dfs(neighbors[i], false);
  32       if (!isRoot && low[neighbors[i]] >= d[v]){
  33         cameras.insert(v);
  34       }
  35       low[v] = min(low[v], low[neighbors[i]]);
  36       ++count;
  37     }else{ // (v, neighbors[i]) is a back edge
  38       low[v] = min(low[v], d[neighbors[i]]);
  39     }
  40   }
  41   if (isRoot && count > 1){ //Is root and has two neighbors in the DFS-tree
  42     cameras.insert(v);
  43   }
  44   colors[v] = BLACK;
  45 }
  46
  47 int main(){
  48   int n;
  49   int map = 1;
  50   while (cin >> n && n > 0){
  51     if (map > 1) cout << endl;
  52     g.clear();
  53     colors.clear();
  54     d.clear();
  55     low.clear();
  56     timeCount = 0;
  57     while (n--){
  58       node v;
  59       cin >> v;
  60       colors[v] = WHITE;
  61       g[v] = vector<node>();
  62     }
  63
  64     cin >> n;
  65     while (n--){
  66       node v,u;
  67       cin >> v >> u;
  68       g[v].push_back(u);
  69       g[u].push_back(v);
  70     }
  71
  72     cameras.clear();
  73
  74     for (graph::iterator i = g.begin(); i != g.end(); ++i){
  75       if (colors[(*i).first] == WHITE){
  76         dfs((*i).first);
  77       }
  78     }
  79
  80     cout << "City map #"<<map<<": " << cameras.size() << " camera(s) found" << endl;
  81     copy(cameras.begin(), cameras.end(), ostream_iterator<node>(cout,"\n"));
  82     ++map;
  83   }
  84   return 0;
  85 }